/**
 * Program 12.4 Array-based symbol table (ordered)
 * -------------------------------------------------------------------------------------------------------
 * Like Program 12.3, this implementation uses an array of items, but without any null items.
 * We keep the array in order when inserting a new item by moving larger items one position to the right
 * in the same manner as insertion sort.
 *
 * The `STsearch` function is a scan through the array that looks for an item with the specified key.
 * Since the array is in order, we know that the search key is not in the table as soon as we encounter an item with
 * a larger key.
 *
 * The `STselect` and `STsort` functions are trivial, and
 * the implementation of STdelete is left as an exercise (see Exercise 12.14).
 */

#include <stdlib.h>

#include "ST.h"

static Item *st;
static int N;

void STinit(int maxN) {
    st = malloc(maxN * sizeof(Item));
    N = 0;
}

int STcount() {
    return N;
}

void STinsert(Item item) {
    int j = N++;
    Key v = key(item);
    while (j > 0 && less(v, key(st[j-1]))) {
        st[j] = st[j-1];
        j--;
    }
    st[j] = item;
}

Item STsearch(Key v) {
    int j;
    for (j = 0; j < N; j++) {
        if (eq(v, key(st[j]))) {
            return st[j];
        }
        if (less(v, key(st[j]))) {
            break;
        }
    }
    return NULLitem;
}

void STdelete(Item item) {
    int i = -1;//记录待删除的item的索引
    int j;
    for (j = 0; j < N; j++) {
        if (eq(key(item), key(st[j]))) {
            i = j;
            break;
        }
        if (less(key(item), key(st[j]))) {
            break;
        }
    }
    if (i != -1) {
        for (j = i; j < N - 1; j++) {
            st[j] = st[j+1];
        }
        N--;
    }
}

Item STselect(int k) {
    return st[k];
}

void STsort(void (*visit)(Item)) {
    int i;
    for (i = 0; i < N; i++) {
        visit(st[i]);
    }
}

